#https://leetcode.cn/problems/longest-increasing-subsequence/submissions/560808718/

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int uu = (int)nums.size();
        // 如果数组为空，直接返回 0
        if (uu == 0) {
            return 0;
        }
        // 初始化动态规划数组 dp，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
        vector<int> dp(uu, 0);
        for (int i = 0; i < uu; ++i) {
            // 遍历之前的元素，寻找可以构成更长递增子序列的机会
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    // 如果前面的元素比当前元素小，更新 dp[i]
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        // 寻找 dp 数组中的最大值，即最长递增子序列的长度
        int sum=0;
        for(int i=0;i<uu;++i) 
            sum=max(sum,dp[i]);
        return sum;
    }
};